/*
 * Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class PascalTriangle2 {
    public ArrayList<Integer> getRow(int rowIndex) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int numRows = rowIndex+1;
        if(numRows == 0)
            return null;
        
        ArrayList<Integer> row = new ArrayList<Integer>();
        row.add(1);
        if(numRows == 1)
            return row;
        
        for(int i = 1; i < numRows; i++)
        {
            ArrayList<Integer> nrow = new ArrayList<Integer>();
            for(int j = 0; j <= i; j++)
            {
                int val;
                if(j == 0 || j == i)
                    val = 1;
                else
                    val = row.get(j-1) + row.get(j);

                nrow.add(val);
            }
            row = nrow;
        }
        
        return row;
    }
}
